The order in which vehicles or other products are built on an assembly line greatly influence the total production cost of the product. There are costs that favor grouping certain options and those that favor spacing others. For example, paint color is an option that will tend to group cars. There is a cost associated with painting consecutive cars different colors that is derived from purging the sprayer nozzle of paint. Another possible cost is the decrease in quality that occurs when colors are changed, due to paint in the air settling on the wrong car. Assuming all cars are of high quality after leaving the paint operation, this would then imply a cost to repaint the car. Two adjacent cars will have a paint cost that is lower if they have the same color than if they have different colors. The cost is however non-symmetric: That is, a white car followed by a black car would have a lower cost than a black car followed by a white car, since it is easier to purge white paint with black paint than vice-versa.
With respect to spacing considerations, an eight-cylinder engine is a good example of an attribute that will suggest that certain cars be spaced far apart during assembly. It takes more time to install an eight-cylinder engine that it does to install a four-or-six-cylinder engine. Thus, it is desirable to leave the maximal space between occurrences of this option. If ten percent of orders have eight-cylinder engines, the best one can do is to space the ones containing these engines every ten cars. Spacing some farther than this will cause others to be spaced closer. If the option is spaced closer than the average, then workers may be rushed. If they are spaced farther apart than the average, there may be idle capacity. Hence there is a cost that is minimum at the average spacing and increases when any spacing deviates from this. The tighter the distribution of spacings cluster around the average, the lower the total cost will be.
Simulated annealing is a randomized local search method for finding near optimum solutions to combinatorial optimization problems and has been discussed extensively in the literature. See for example Optimization by Simulated Annealing by S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science Volume 220, Page 671-680. The method is particularly applicable to problems where the number of possible solutions is extremely large and there is no efficient way to examine each possible solution. In U.S. Pat. No. 4,495,559 simulated annealing is applied to the problem of integrated circuit placement and layout.
Simulated annealing finds a minimum of an objective function ##EQU1##
where the symbol x represents the set of variables which completely specify the configuration of the objects which compose the combinatorial problem. Each term (labeled by i), called an objective, in Eq. 1 is associated with some attribute of the configuration and is designed to decrease when the configuration possesses a desired arrangement of that attribute.
Simulated annealing searches out a minimum of Eq. 1 by making a series of successive changes from some starting configuration. Let DELTA x be such a change and DELTA 0=0(x +DELTA x)-0(x) the corresponding change in 0(x). If DELTA 0 is negative, simulated annealing accepts the changed configuration. If DELTA 0 is positive, simulated annealing accepts the changed configuration with probability EQU P=exp (-DELTA 0/T), (2)
where T is a parameter, called the temperature, which changes during the course of the simulated annealing run according to an annealing schedule. A possible schedule is shown in FIG. 1. Essential properties of an annealing schedule are that the temperature be "high" for some period at the beginning of the schedule and decrease to a "low" value at the end. During the high part of the schedule, simulated annealing accepts many unfavorable changes and thus explores many configurations. As the temperature decreases the method is designed to settle into a minimum of 0(x). If the run is long enough and the cooling slow enough, it can be proved that simulated annealing will find the absolute minimum of 0(x).
The difficulty with simulated annealing is that with some problems so much computer time is required that the method is not practical for such problems. Run time can be unacceptably long when some of the desired configurations conflict with one another, i.e., when a change which decreases one of the terms of Eq. 1 almost always increases another.